package demo.exam;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test03 {

	public static void main(String[] args) {
		System.out.println(doAction(8, 15, 8, 1, Arrays.asList(
				Arrays.asList(1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1),
				Arrays.asList(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
				Arrays.asList(1, 2, 1, 2, 1, 0, 1, 3, 2, 2, 2, 1, 2, 2, 2),
				Arrays.asList(1, 2, 1, 2, 2, 0, 1, 3, 1, 2, 1, 2, 1, 2, 1),
				Arrays.asList(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
				Arrays.asList(2, 1, 2, 2, 2, 0, 2, 2, 1, 1, 0, 1, 2, 1, 2),
				Arrays.asList(2, 2, 2, 2, 2, 0, 2, 2, 2, 2, 0, 2, 2, 2, 2),
				Arrays.asList(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0))));
	}

	private static String doAction(int m, int n, int row, int column, List<List<Integer>> area) {
		PathTree root = new PathTree();
		root.row = row - 1;
		root.column = column - 1;
		area.get(root.row).set(root.column, 4); // 表示计算过

		ArrayList<PathTree> parent = new ArrayList<>();
		parent.add(root);

		ArrayList<PathTree> children = new ArrayList<>();
		ArrayList<PathTree> result = new ArrayList<>();

		while (result.size() == 0) {
			// printTable(m, n, area);
			for (int index = 0; index < parent.size(); index++) {
				PathTree node = parent.get(index);
				if (node.row > 0) {
					int cellArea = area.get(node.row - 1).get(node.column);
					if (cellArea == 0) {
						// 车道
						area.get(node.row - 1).set(node.column, 4);
						children.add(createNode(node.row - 1, node.column, node));
					}
					if (cellArea == 1) {
						// 空位
						result.add(createNode(node.row - 1, node.column, node));
					}
				}
				if (node.row < m - 1) {
					int cellArea = area.get(node.row + 1).get(node.column);
					if (cellArea == 0) {
						// 车道
						area.get(node.row + 1).set(node.column, 4);
						children.add(createNode(node.row + 1, node.column, node));
					}
					if (cellArea == 1) {
						// 空位
						result.add(createNode(node.row + 1, node.column, node));
					}
				}
				// 左
				if (node.column > 0) {
					// int newRow = node.row;
					int cellArea = area.get(node.row).get(node.column - 1);
					if (cellArea == 0) {
						// 车道
						area.get(node.row).set(node.column - 1, 4);
						children.add(createNode(node.row, node.column - 1, node));
					}
				}
				if (node.column < n - 1) {
					int cellArea = area.get(node.row).get(node.column + 1);
					if (cellArea == 0) {
						// 车道
						System.out.println("R:" + node.row + " + " + (node.column + 1));
						area.get(node.row).set(node.column + 1, 4);
						children.add(createNode(node.row, node.column + 1, node));
					}
				}

			}
			parent.clear();
			parent.addAll(children);
			children.clear();
		}

		ArrayList<PathTree> result2 = new ArrayList<>();
		int minRow = m + 1;
		int minColumn = n + 1;
		for (int index = 0; index < result.size(); index++) {
			PathTree node = result.get(index);
			if (node.row < minRow) {
				minRow = node.row;
				minColumn = node.column;
			} else if (node.row == minRow && node.column < minColumn) {
				minColumn = node.column;
			}
		}
		System.out.println(minRow + ":" + minColumn);
		for (int index = 0; index < result.size(); index++) {
			PathTree node = result.get(index);
			if (node.row == minRow && node.column == minColumn) {
				result2.add(node);
			}
		}

		return outputPath(result2.get(0));
	}

	private static PathTree createNode(int row, int column, PathTree parent) {
		// System.out.println(row + ":" + column);
		PathTree node = new PathTree();
		node.row = row;
		node.column = column;
		node.parent = parent;
		return node;
	}

	private static String outputPath(PathTree node) {
		String path = (node.row + 1) + " " + (node.column + 1);
		PathTree parent = node.parent;
		while (parent != null) {
			path = (parent.row + 1) + " " + (parent.column + 1) + " " + path;
			parent = parent.parent;
		}
		return path;
	}

	private static void printTable(int m, int n, List<List<Integer>> result) {
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				Integer cell = result.get(i).get(j);
				System.out.print(cell + ", ");
			}
			System.out.println("");
		}
		System.out.println("\n\n");
	}
}
